Pada sekitar tahun 1999, Zul 2 by 2 atau nama sebenarnya, Zulkefli Majid yang merupakan Artist & Repertoire (A&R) di syarikat rakaman Suria Records (SRC), telah ditugaskan untuk melahirkan artis-artis baharu dalam usaha untuk memeriahkan lagi industri muzik tanah air. Suria Records pada ketika itu merupakan sebuah sebuah nama besar yang telah melahirkan beberapa artis ternama seperti Noraniza Idris dan Siti Nurhaliza (kini Datuk) dengan lagu-lagu mereka yang bergenre pop melayu dan tradisional. Senario muzik tempatan yang pada ketika itu banyak tertumpu pada genre pop rock telah memberi idea untuk Zul menubuhkan sebuah kumpulan muzik yang terdiri daripada kalangan remaja. Maka dengan itu, beliau telah menjemput kumpulan-kumpulan remaja yang aktif di sekitar Kuala Lumpur untuk diuji bakat dalam merealisasikan ideanya itu. Dalam sesi uji bakat tersebut, Zul telah memilih lima orang remaja daripada latar belakang yang berbeza iaitu Shah Indrawan bin Ismail (Tomok - Vokal, 15 tahun), Shahrizan bin Mat Salleh (Jay - Gitar Utama, 17 tahun), Zarimi bin Zahari (Zimi - Gitar Kedua, 15 tahun), Mohd Syukri bin Shanusi (Syuk - Bass, 16 tahun) dan Mat Shah bin Mat Salleh (Along - Dram, 19 tahun). Hasil perbincangan Zul bersama pengurusnya, akhirnya Zul telah menamakan kumpulan anak-anak muda ini sebagai New Boyz sekaligus mengikat kontrak sebagai artis rakaman Suria Records. Namun belum sempat New Boyz memulakan sesi rakaman, Zimi telah menarik diri kerana penyertaannya bersama New Boyz tidak direstui ibu bapanya pada ketika itu. Tempatnya kemudian digantikan oleh seorang remaja berusia 16 tahun bernama Mazlan bin Ismail atau lebih dikenali sebagai Lan.

Akhirnya pada tahun 1999, New Boyz telah muncul dengan album pertama yang menggunakan nama mereka sebagai judul album. Album ini telah memperkenalkan nama mereka dalam industri muzik tanah air apabila single pertamanya yang berjudul Sejarah Mungkin Berulang, ciptaan Zul & lirik oleh Lukhman S menjadi siulan ramai seterusnya mencatatkan jualan melebihi 100,000 unit bukan sahaja di Malaysia, malah diterima baik di Indonesia, Singapura dan Brunei. Kejayaan album pertama ini membolehkan mereka menerima anugerah platinum daripada pihak syarikat rakaman dan secara tidak langsung menjadikan New Boyz antara kumpulan remaja paling popular pada ketika itu. Bukan itu sahaja, mereka juga tercalon dalam Anugerah Bintang Popular Berita Harian (ABPBH) bagi kategori Artis Berkumpulan Paling Popular pada tahun 2001. Selain ABPBH, New Boyz turut pernah tercalon dalam Anugerah Industri Muzik dan Anugerah Planet Muzik dalam tempoh tersebut. New Boyz terus mengorak langkah dengan menghasilkan album kedua yang diberi judul Akur pada tahun 2000. Album ini turut meletup di pasaran dengan lagu yang berjudul Meraung, ciptaan Zul dan lirik oleh Mama Juwie (Allahyarham) sekaligus menjadikan lagu ini lebih popular daripada lagu-lagu mereka yang sebelumnya.

Pada tahun 2001, New Boyz mengalami pertukaran anggota apabila Radin Irwan Dzulkarnain bin Isagani atau Zack dipilih oleh Suria Records untuk menggantikan Syuk. Dengan kemasukan Zack sebagai pemain bass baharu, New Boyz menghasilkan dua album yang berjudul Wirama dan Inspirasi, masing-masing pada tahun 2001 dan 2002.

Namun atas komitmen dan hala tuju yang berlainan, Lan, Jay dan Along telah menarik diri daripada New Boyz selepas album Wirama, sekaligus meninggalkan Tomok dan Zack sebagai anggota yang kekal. Tempat mereka kemudiannya digantikan oleh dua pemuzik baharu iaitu Ridza Faitullah (Rizz - Gitar Utama) dan Wan Muzaffar (Ristoe - Dram). Dengan line-up baharu ini, New Boyz menghasilkan album kelima yang berjudul Bermulanya Satu Evolusi pada tahun 2004.

Kemudian pada tahun 2007, sekali lagi New Boyz bertukar anggota di mana kali ini pemain gitar utamanya, Rizz keluar dan digantikan oleh Hafeez As'ad bin Azam atau lebih dikenali sebagai Afiez. Afiez mempunyai pengalaman dalam bidang muzik dan sebelum ini pernah menjadi pemuzik kelab di sekitar Kuala Lumpur dan Pulau Pinang. Sentuhan gitar Afiez disumbangkan dalam album keenam New Boyz iaitu Semula Padaku. Album ini turut membariskan beberapa komposer terkenal seperti Taja Meet Uncle Hussain, Along Exists, Edry KRU dan ramai lagi. Selain daripada menggunakan khidmat komposer luar, anggota New Boyz sendiri mengambil peluang dalam penciptaan lagu untuk album tersebut. Antaranya ialah lagu yang dicipta sepenuhnya oleh Tomok dengan lagu Kau Bernama Cinta. Lagu ini merupakan antara lagu yang menjadi hit dalam album tersebut dan kerap diputarkan di corong-corong radio tempatan.

Setelah penghasilan album Semula Padaku, New Boyz seakan menyepi disebabkan penjualan album yang tidak memberangsangkan ekoran keadaan ekonomi yang tidak menentu dan penjualan album yang terbantut yang dialami oleh keseluruhann artis Malaysia. Selepas dua tahun menyepi, New Boyz akhirnya muncul dengan dua single terbaru mereka iaitu Kau Pergi dan Terima Kasih (Hero) di mana penciptaan lagu sehingga proses penghasilan keseluruhan kedua-dua lagu dibuat sepenuhnya oleh mereka sendiri pada tahun 2008. Lagu Kau Pergi merupakan lagu ciptaan sepenuhnya oleh Tomok dan lagu Terima Kasih (Hero) merupakan lagu pertama ciptaan Zack selaku pemain bass New Boyz. Pada tahun 2010, lagu Terima Kasih (Hero) telah menjadi salah satu lagu soundtrack bagi filem KAPOWW!! - Atoi The Kultur Boy yang mana judulnya telah ditukar menjadi Roket Ke Langit, malah terdapat sedikit perubahan lirik dalam lagu tersebut.

Belumpun sebulan single itu dihasilkan Tomok pula mengambil keputusan untuk menyertai satu pertandingan program realiti One In A Million musim ketiga pada tahun 2009 dan dinobatkan sebagai Juara. Penyertaan Tomok dalam program realiti itu telah menjadi isu dan diperkatakan oleh masyarakat dan ada yang mengandaikan Tomok telah bergerak secara SOLO dan meninggalkan ahli kumpulannya yang lain, sekaligus tidak lagi bergelar vokalis kumpulan New Boyz. Tetapi Tomok telah menafikan dakwaan itu dan mengesahkan bahawa dia masih lagi penyanyi untuk kumpulan New Boyz. Tomok tidak pernah terfikir untuk meninggalkan kumpulan New Boyz sama sekali dan menyatakan penyertaannya itu mendapat restu dan sokongan dari ahli New Boyz yang lain.

Sehingga kini, New Boyz masih lagi kekal berempat hanya menunggu masa dan waktu yang sesuai untuk mempertaruhkan hasil kerja mereka yang seterusnya. Dikhabarkan mereka akan tumpukan perhatian dalam pembikinan album mereka sepenuhnya selepas Tomok selesai menghasilkan album solo beliau dalam masa terdekat. Kini New Boyz mahu lebih dikenali sebagai NB iaitu singkatan untuk New Boyz itu sendiri.

Along, Jay dan Lan telah membentuk sebuah band yang dikenali sebagai Funkiey Band dan menambah 2 orang anak muda, manakala Syuk tidak lagi aktif dalam bidang muzik kerana telah terlibat dengan Club Syarikat Alza. Afiez selaku gitaris utama kemudiannya tidak aktif bersama New Boyz dan telah menyertai Kumpulan Akim & The Majistret sebagai pemain keyboard, bukan lagi sebagai gitaris.

Pada tahun 2019, vokalis New Boyz iaitu Tomok telah memberi bayangan untuk membuat penyatuan semula New Boyz dengan cuba memanggil semula anggota-anggota yang pernah bersama New Boyz iaitu Zack, Afiez, Ristoe, Lan, Jay, Syuk, Along dan Rizz.